-- | A generic implementation of Branch & Bound

{-# LANGUAGE TupleSections #-}

module BB (C(..), inf) where

import qualified Iv
import Interlude
import qualified Data.List.Ordered as OrdList

class Show b => C b where
  type Bound b
  branch :: b -> [b]
  bounds :: b -> Iv.T (Bound b)
  -- ^ Calls to bounds must be cached.

-- | Returns an interval containing the infimum.
inf :: (BB.C b, Ord (Bound b), Show (Bound b)) => (Iv.T (Bound b) -> Bool) -> Int -> b -> Writer String (Iv.T (Bound b))
inf term v = \b0 -> inf_ [b0] (Iv.hi $ bounds b0) where
  inf_ (b@(Iv.lo . bounds -> lb) : bs) u =
    when (v >= 1) (tellLn $ printf "[%-22s, %-22s] (holding %s)" (show lb) (show u)
       (pluralSfx (length bs + 1) "box" "es")) >>
    when (v == 2) (tellLn $ show b ++ "\n") >>
    when (v >= 3) (tellLn $ unlines (map show (b:bs))) >>
    if term answer then
      when (v >= 0) (tellLn ("\nThe minimum lies in:\n" ++ show answer)) >>
      return answer
    else inf_ (takeWhile (not . (u' <) . Iv.lo . bounds)
           $ OrdList.mergeBy cmp b' bs) u'
    where cmp = compare `on` Iv.lo . bounds
          b' = OrdList.sortBy cmp $ branch b
          u' = foldr (min . Iv.hi . bounds) u b'
          answer = Iv.mk lb u
  inf_ _ _ = error "inf: the problem evaporated"
    -- This may happen with floating point numbers on Intel processors.
